package q1135_minimumCost;

import java.util.*;

public class Solution_2 {
    /*
    一个使用prim的方法
     */
    public int minimumCost(int n, int[][] connections) {
        List<List<int[]>> graph = buildGraph(n, connections);
        Prim prim = new Prim(graph);
        if (!prim.allConnected()) return -1;
        return prim.weightSum;
    }
    /*
    构建一个图g
    其初始容量为n+1（这个0的位置只是存了一个空list，为了简化后面用get直接用对应序号，而不用减1）
    g中存储了每一个点i到其他所有点j的边的长度 也就是一个 i : {..., (i + 1, len1), (i + 2, len2), ...}
     */
    List<List<int[]>> buildGraph(int n, int[][] connections) {
        List<List<int[]>> graph = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] c : connections) {
            graph.get(c[0]).add(new int[]{c[1], c[2]});
            graph.get(c[1]).add(new int[]{c[0], c[2]});
        }
        return graph;


    }

    class Prim {
        PriorityQueue<int[]> pq;
        boolean[] visited;
        int weightSum;
        List<List<int[]>> graph;
        int n;

        Prim(List<List<int[]>> graph) {
            this.graph = graph;
            this.pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
            this.n = graph.size();
            this.visited = new boolean[n];
            this.weightSum = 0;
            // 先随意选一个点，我们这里选择1号点作为开始
            visited[1] = true;
            cut(1);
            while (!pq.isEmpty()) {
                int[] tmp = pq.poll();
                int to = tmp[0];
                int weight = tmp[1];
                // 已经在树中，跳过，否则成环
                if (visited[to]) continue;
                // 加入树中
                visited[to] = true;
                weightSum += weight;
                cut(to);
            }
        }

        boolean allConnected() {
            for (int i = 1; i < n; i++) {
                if (!visited[i]) return false;
            }
            return true;
        }

        void cut(int s) {
            for (int[] ints : graph.get(s)) {
                int to = ints[0];
                // 已经在树中，跳过，否则成环
                if (visited[to]) continue;
                // 入优先级队列
                pq.offer(ints);
            }
        }
    }

}

